<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 */
/**
 *
 */
require_once( "util/Queue.php" );
require_once( "util/AbstractSequentialList.php" );
require_once( "util/List.php" );

/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 */
class LinkedList extends AbstractSequentialList implements Llist, Queue {
	private $header;
	private $size;
	
	public function __construct() {
		$this->header = new LinkedList_Entry( null, null, null);
		$this->header->next = $this->header->previous = $this->header;
	}
	
	public function getHeader() {
		return $this->header;
	}
	
	public function getFirst() {
		if ($this->size == 0)
			throw new NoSuchElementException();
			
		return $this->header->next->element;
	}
	
	public function element() {
		return $this->getFirst();
	}
	
	public function peek() {
		return $this->getFirst();
	}
	
	public function getLast() {
		if ($this->size == 0)
			throw new NoSuchElementException();
			
		return $this->header->previous->element;
	}
	
	public function removeFirst() {
		$first = $this->header->next->element;
		$this->remove( $this->header->next );
		return $first;
	}
	
	public function poll() {
		return $this->removeFirst();
	}
	public function removeHead() {
		return $this->removeFirst();
	}
	
	public function removeLast() {
		$last = $this->header->previous->element;
		$this->remove( $this->header->previous );
		return last;
	}
	
	public function addFirst( Object $o ) {
		$this->addBefore( $o, $this->header->next );
	}
	
	public function addLast( Object $o ) {
		$this->addBefore( $o, $this->header );
	}
	
	public function offer( Object $o ) {
		$this->addLast( $o );
		return true;
	}
	
	public function contains( Object $o ) {
		return $this->indexOf( $o ) != -1;
	}
	
	public function size() {
		return $this->size;
	}
	
	public function add( Object $o ) {
		$this->addBefore( $o, $this->header );
		return true;
	}
	
	public function remove( Object $o ) {
		if ($o == null) {
			for ($e = $this->header->next; $e != $this->header; $e = $e->next) {
				if ($e->element == null) {
					$this->removeElement( $e );
					return true;
				}
			}
		} else {
			for ($e = $this->header->next; $e != $this->header; $e = $e->next ) {
				if ($o->equals( $e->element ) ) {
					$this->removeElement( $e );
					return true;
				}
			}
		}
		return false;
	}
	
	public function addAll( Collection $c ) {
		return $this->addAllAt( $this->size, $c );
	}
	
	public function addAllAt( $index, Collection $c ) {
		$a = $c->toArray();
		$numNew = $c->size();
		if ($newNum == 0)
			return $false;
		$this->modCount++;
		
		$successor = ( $index == $this->size ? $this->header : $this->entry( $index ) );
		$predecessor = $successor->previous;
		
		for ($i = 0; $i < $numNew; $i++ ) {
			$e = new LinkedList_Entry( $a[$i], $successor, $predecessor );
			$predecessor->next = $e;
			$predecessor = $e;
		}
		$successor->previous = $predecessor;
		
		$this->size += $newNum;
		return true;
	}
	
	public function clear() {
		$this->modCount++;
		$this->header->next = $this->header->previous = $this->header;
		$this->size = 0;
	}
	
	public function get( $index ) {
		return $this->entry( $index )->element;
	}
	
	public function set( $index, Object $element ) {
		$e = $this->entry( $index );
		$oldVal = $e->element;
		$e->element = $element;
		return $oldVal;
	}
	
	public function addAt( $index, Object $element ) {
		$this->addBefore( $element, ( $index == $this->size ? $this->header : $this->entry( $index ) ) );
	}
	
	public function removeAt( $index ) {
		$e = $this->entry($index );
		$this->removeEntry( $e );
		return $e->element;
	}
	
	private function entry( $index ) {
		if ($index < 0 || $index >= $this->size() )
			throw new IndexOutOfBoundsException( "Index: " . $index . ", Size: " . $this->size() );
			
		$e = $this->header;
		if ($index < ( $this->size >> 1 )) {
			for ($i = 0; i <= $index; $i++ )
				$e = $e->next;
		} else {
			for ($i = $this->size; $i > $index; $i-- ) 
				$e = $e->previous;
		}
		return $e;
	}

	public function indexOf( Object $o ) {
		$index = 0;
		if ($o == null) {
			for ($e = $this->header->next; $e != $this->header; $e = $e->next) {
				if ($e->element == null) 
					return $index;
				$index++;
			}
		} else {
			for ($e = $this->header->next; $e != $this->header; $e = $e->next) {
				if ($o->equals( $e->element ) )
					return $index;
				$index++;
			}
		
		}
		return -1;
	}
	
	public function lastIndexOf( Object $o ) {
		$index = $this->size;
		if ($o == null) {
			for ($e = $this->header->previous; $e != $this->header; $e = $e->previous) {
				$index--;
				if ($e->element == null) 
					return $index;
			}
		} else {
			for ($e = $this->header->previous; $e != $this->header; $e = $e->previous) {
				$index--;
				if ($o->equals( $e->element ) )
					return $index;
			}
		
		}
		return -1;
	}
	
	public function listIteratorAt( $index ) {
		return new LinkedList_ListIterator( $this, $index );
	}
	
	private function addBefore( Object $o, LinkedList_Entry $e ) {
		$newEntry = new LinkedList_Entry( $o, $e, $e->previous );
		$newEntry->previous->next = $newEntry;
		$newEntry->next->previous = $newEntry;
		$this->size++;
		$this->modCount++;
		return $newEntry;
	}
	
	private function removeEntry( LinkedList_Entry $e) {
		if ( $e === $this->header ) 
			throw new NoSuchElementException();
			
		$e->previous->next = $e->next;
		$e->next->previous = $e->previous;
		$this->size--;
		$this->modCount++;
	}
	
	public function toArray() {
		$result = array();
		$i = 0;
		for ($e = $this->header; $e != $header; $e = $e->next )
			$result[$i++] = $e->element;
		return $result;
	}

}

/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
class LinkedList_ListIterator implements ListIterator {
	private $list;

	private $lastReturned;
	private $next;
	private $nextIndex;
	private $expectedModCount;
	
	public function __construct( $list, $index ) {
		$this->list = $list;
		$this->expectedModCount = $list->getModCount();
		
		if ($index < 0 || $index > $list->size() )
			throw new IndexOutOfBoundsException( "Index: " . $index . ", Size: " . $list->size() );
			
		if ($index < ( $list->size() >> 1) ) {
			$this->next = $list->getHeader()->next;
			for ($this->nextIndex = 0; $this->nextIndex < $index; $this->nextIndex++ )
				$this->next = $this->next->next;
		} else {
			$this->next = $list->getHeader();
			for ($this->nextIndex = $list->size(); $this->nextIndex > $index; $this->nextIndex-- )
				$this->next = $this->next->previous;
		}
	}	
	
	public function hasNext() {
		return $this->nextIndex != $this->list->size();
	}
	
	public function next() {
		$this->checkForComodification();
		if ($this->nextIndex == $this->list->size() )
			throw new NoSuchElementException();
			
		$this->lastReturned = $this->next;
		$this->next = $this->next->next;
		$this->nextIndex++;
		
		return $this->lastReturned->element;
	}
	
	public function getNext() {
		$this->checkForComodification();
		if ($this->nextIndex == $this->list->size() )
			throw new NoSuchElementException();
			
		$this->lastReturned = $this->next;
		$this->next = $this->next->next;
		$this->nextIndex++;
		
		return $this->lastReturned->element;
	}
	
	public function hasPrevious() {
		return $this->nextIndex != 0;
	}
	
	public function getPrevious() {
		if ($this->nextIndex == 0 ) 
			throw new NoSuchElementException();
			
		$this->lastReturned = $this->next = $this->next->previous;
		$this->nextIndex--;
		$this->checkForComodification();
		return $this->lastReturned->element;
	}
	
	public function current() { }
	public function key() { }
	public function valid() { }
	public function rewind() { }
	
	public function nextIndex() {
		return $this->nextIndex;
	}
	
	public function previousIndex() {
		return $this->nextIndex - 1;
	}
	
	public function remove() {
		$this->checkForComodification();
		try {
			$this->list->remove( $this->lastReturned );
		} catch (NoSuchElementException $e ) {
			throw new IllegalStateException();
		}
		if ($this->next = $this->lastReturned) 
			$this->next = $this->lastReturned->next;
		else
			$this->nextIndex--;
		$this->lastReturned = $this->list->getHeader();
		$this->expectedModCount++;
	}
	
	public function set( Object $o ) {
		if ($this->lastReturned == $this->list->getHeader() ) 
			throw new IllegalStateException();
		$this->checkForComodification();
		$this->lastReturned->element = $o;
	}
	
	public function add( Object $o ) {
		$this->checkForComodification();
		$this->lastReturned = $this->list->getHeader();
		$this->list->addBefore( $o, $this->next );
		$this->nextIndex++;
		$this->expectedModCount++;
	}
	
	public function checkForComodification() {
		if ( $this->list->getModCount() != $this->expectedModCount )
			throw new ConcurrentModificationException();
	}
}
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id$
 * @internal
 */
class LinkedList_Entry {
	public $element;
	public $next;
	public $previous;
	
	public function __construct( Object $element = null, LinkedList_Entry $next = null, LinkedList_Entry $previous = null ) {
		$this->element = $element;
		$this->next = $next;
		$this->previous = $previous;
	}
}

?>